/*
 * The RavenX Library
 * Copyright (c) 2008 by Solidus
 * 
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.It is provided "as is" without express 
 * or implied warranty.
 *
 */
#include "rx_hashtable.h"
#include "rx_mem.h"
#include "rx_debug.h"
#include "rx_misc.h"

RX_SPACE_BEG




typedef struct __rx_hash_node_tag
{
		rx_hash_node_t	*next;
}rx_hash_node_t;
#define __hash_node_size(esize) (esize + sizeof(rx_hash_node_t))
#define __hash_node_data(node)  ((void*)((rx_byte*)(node) + sizeof(rx_hash_node_t)))


typedef struct __rx_hashtable_tag
{
		rx_hash_node_t			**buckets;
		size_t					bucket_size;
		size_t					elem_count;

		rx_hash_node_t			*free_list;
/*
		rx_hash_func_t			hash_f;
		rx_copy_new_func_t		copy_f;
		rx_destroy_func_t		destroy_f;
		rx_cmp_func_t			cmp_f;
		rx_key_func_t			key_f;
*/
		rx_info_t				info;
		rx_alloc_t				alloc;

}rx_hashtable_t;






static RX_INLINE rx_bool __hashtable_is_valid(const rx_hashtable_t *self)
{
		if(self == NULL) return rx_false;

		if(!(self->info.hash_f != NULL && self->info.copy_f != NULL && self->info.init_f != NULL && self->info.uninit_f  != NULL && self->info.cmp_f != NULL && self->info.key_f)) return rx_false;

		if(self->info.elem_size == 0 || self->info.key_elem_size == 0)return rx_false;

		if(self->alloc.alloc_f == NULL  || self->alloc.dealloc_f == NULL || self->alloc.realloc_f == NULL) return rx_false;
		
		if(self->bucket_size > 0 && self->buckets == NULL)return rx_false;

		return rx_true;
}


static RX_INLINE rx_hash_node_t* __create_node(const void *sour, rx_hashtable_t *self)
{
		rx_hash_node_t *res;
		
		if(self->free_list != NULL)
		{
				res = self->free_list;
				self->free_list = self->free_list->next;
		}else
		{
				res = (rx_hash_node_t*)self->alloc.alloc_f(__hash_node_size(self->info.elem_size), self->alloc.ctx);
				self->info.init_f(__hash_node_data(res), self->info.elem_size);
		}
		RX_FATAL_ERROR((res != NULL) && "Can't alloc memory!");
		
		res->next = NULL;
		self->info.copy_f(__hash_node_data(res), sour, self->info.elem_size);
		return res;
}


static RX_INLINE void __destroy_node(rx_hash_node_t *node, rx_hashtable_t *self)
{
		if(node != NULL)
		{
				RX_ASSERT(__hashtable_is_valid(self));
				self->info.uninit_f(__hash_node_data(node), self->info.elem_size);
				node->next = self->free_list;
				self->free_list = node;
		}
}

static RX_INLINE void __clear_free_nodes(rx_hashtable_t *self)
{
		rx_hash_node_t *tmp;
		RX_ASSERT(__hashtable_is_valid(self));
		
		while(self->free_list != NULL)
		{
				tmp = self->free_list;
				self->free_list = tmp->next;
				self->alloc.dealloc_f(tmp, self->alloc.ctx);
		}
}


/*****************************************************************/


#define __n_primers 28

static const size_t  __prime_list[__n_primers] =
{
  53,         97,           193,         389,       769,
  1543,       3079,         6151,        12289,     24593,
  49157,      98317,        196613,      393241,    786433,
  1572869,    3145739,      6291469,     12582917,  25165843,
  50331653,   100663319,    201326611,   402653189, 805306457, 
  1610612741, 3221225473ul, 4294967291ul
};

static RX_INLINE size_t __next_prime(size_t curr)
{
		int l = 0, r = __n_primers - 1;
		const size_t *res = NULL;

		while(l <= r)
		{
				int m = (l + r)/2;
				if(__prime_list[m] <= curr)
				{
						l = m + 1;
				}else
				{
						res = __prime_list + (size_t)m;
						r = m - 1;
				}
		}

		return res != NULL ? *res : 4294967291ul;
}

static RX_INLINE size_t __calc_bknum_key_n(const rx_hashtable_t *self, const void *key, size_t bucket_size)
{
		RX_ASSERT(__hashtable_is_valid(self));
		RX_ASSERT(bucket_size > 0);
		return self->info.hash_f(key, self->info.key_elem_size) % bucket_size;

}

static RX_INLINE size_t __calc_bknum_key(const rx_hashtable_t *self, const void *key)
{
		RX_ASSERT(__hashtable_is_valid(self));
		return __calc_bknum_key_n(self, key, self->bucket_size);
	
}


static RX_INLINE size_t __calc_bknum(const rx_hashtable_t *self, const void *data)
{
		return __calc_bknum_key(self, self->info.key_f(data));
}

static RX_INLINE rx_hash_node_t* __insert_equal_noresize(rx_hashtable_t *self, const void *data)
{
		rx_hash_node_t *first, *new_node;
		size_t idx;
		RX_ASSERT(__hashtable_is_valid(self));

		idx =__calc_bknum(self, data);
		new_node = __create_node(data, self);
		if(self->buckets[idx] == NULL)
		{
				self->buckets[idx] = new_node;
		}else
		{
				first = self->buckets[idx];
				
				while(first != NULL)
				{
						if(self->info.cmp_f(self->info.key_f(__hash_node_data(first)), self->info.key_f(data), self->info.key_elem_size) == 0)
						{
								new_node->next = first->next;
								first->next = new_node;
								break;
						}else
						{
								first = first->next;
						}
				}
				if(first == NULL)
				{
						new_node->next = self->buckets[idx];
						self->buckets[idx] = new_node;
				}
		}
		
		self->elem_count++;
		return new_node;

}



static RX_INLINE rx_hash_node_t* __insert_unique_noresize(rx_hashtable_t *self, const void *data)
{
		rx_hash_node_t *first, *new_node;
		size_t idx;
		RX_ASSERT(__hashtable_is_valid(self));
		
		new_node = NULL;
		idx =__calc_bknum(self, data);
		
		if(self->buckets[idx] == NULL)
		{
				new_node = __create_node(data, self);
				self->buckets[idx] = new_node;
				self->elem_count++;
		}else
		{
				first = self->buckets[idx];
				
				while(first != NULL)
				{
						if(self->info.cmp_f(self->info.key_f(__hash_node_data(first)), self->info.key_f(data), self->info.key_elem_size) == 0)
						{
								return NULL;
						}else
						{
								first = first->next;
						}
				}
				
				new_node = __create_node(data, self);
				new_node->next = self->buckets[idx];
				self->buckets[idx] = new_node;
				self->elem_count++;
		}
		
		return new_node;
}

static RX_INLINE void __inc_buk_resize(rx_hashtable_t *self, size_t inc_n)
{
		size_t new_size, idx;
		rx_hash_node_t **new_buks;
		
		RX_ASSERT(__hashtable_is_valid(self));
		
		if(inc_n == 0)return;

		new_size = __next_prime(self->elem_count + inc_n);
		if(new_size <= self->bucket_size)
		{
				return;
		}


		new_buks = (rx_hash_node_t**)self->alloc.alloc_f(sizeof(rx_hash_node_t*) * new_size, self->alloc.ctx);
		if(new_buks == NULL)return;
		
		for(idx = 0; idx < new_size; ++idx)new_buks[idx] = NULL;

		for(idx = 0; idx < self->bucket_size; ++idx)
		{
				rx_hash_node_t *curr = self->buckets[idx];
				
				while(curr != NULL)
				{
						rx_hash_node_t *tmp;

						size_t new_idx = __calc_bknum_key_n(self, self->info.key_f(__hash_node_data(curr)), new_size);
						tmp = curr->next;
						curr->next = new_buks[new_idx];
						new_buks[new_idx] = curr;
						curr = tmp;
				}
		}

		self->alloc.dealloc_f(self->buckets, self->alloc.ctx);
		self->buckets = new_buks;
		self->bucket_size = new_size;
}


/*****************************************************************/


void			 rx_hashtable_swap(rx_hashtable_t *left, rx_hashtable_t *right)
{
		rx_hashtable_t tmp;
		RX_ASSERT(__hashtable_is_valid(left));
		RX_ASSERT(__hashtable_is_valid(right));
		
		tmp = *left;
		*left = *right;
		*right = tmp;
		
		RX_ASSERT(__hashtable_is_valid(left));
		RX_ASSERT(__hashtable_is_valid(right));

}

size_t rx_hashtable_bucket_size(const rx_hashtable_t *self)
{
		RX_ASSERT(__hashtable_is_valid(self));
		return self->bucket_size;

}


size_t rx_hashtable_bucket_node_size(const rx_hashtable_t *self, size_t i)
{
		size_t n;
		rx_hash_node_t *curr;
		RX_ASSERT(__hashtable_is_valid(self));
		RX_ASSERT(i < self->bucket_size);
		n = 0;
		for(curr = self->buckets[i]; curr != NULL; curr = curr->next)n++;
		return n;
}

rx_hash_node_t* rx_hashtable_node_next(const rx_hashtable_t *self, rx_hash_node_t *node)
{
		RX_ASSERT(__hashtable_is_valid(self));

		if(node == NULL)return NULL;
		
		if(node->next == NULL)
		{
				size_t idx = __calc_bknum(self, __hash_node_data(node)) + 1;
				node = NULL;
				while(idx < self->bucket_size && node == NULL) node = self->buckets[idx++];
				return node;
		}else
		{
				return node->next;
		}
}

rx_hash_node_t* rx_hashtable_node_first(const rx_hashtable_t *self)
{
		size_t i; 
		RX_ASSERT(__hashtable_is_valid(self));
		
		for(i = 0; i < self->bucket_size; ++i)
		{
				if(self->buckets[i] != NULL) return self->buckets[i];
		}

		return NULL;

}


void*			rx_hashtable_node_data(rx_hash_node_t *node)
{
		return node == NULL ? NULL : __hash_node_data(node);

}



rx_hash_node_t* rx_hashtable_insert_unique(rx_hashtable_t *self, const void *data)
{
		RX_ASSERT(__hashtable_is_valid(self));
		__inc_buk_resize(self, 1);
		return __insert_unique_noresize(self, data);
}

rx_hash_node_t* rx_hashtable_insert_equal(rx_hashtable_t *self, const void *data)
{
		RX_ASSERT(__hashtable_is_valid(self));
		__inc_buk_resize(self, 1);
		return __insert_equal_noresize(self, data);

}



rx_hash_node_t* rx_hashtable_erase_node(rx_hashtable_t *self, rx_hash_node_t *node)
{
		size_t idx;
		rx_hash_node_t **curr, *next;
		RX_ASSERT(__hashtable_is_valid(self));
		RX_ASSERT(node != NULL);
		
		next = rx_hashtable_node_next(self, node);

		idx = __calc_bknum(self, __hash_node_data(node));
		curr = &self->buckets[idx];
		RX_ASSERT(*curr != NULL);

		while(*curr != NULL)
		{
				if(*curr == node)
				{
						*curr = node->next;
						self->elem_count--;
						break;
				}else
				{
						curr = &(*curr)->next;
				}
		}

		return next;
		
}

rx_hash_node_t* rx_hashtable_erase_range(rx_hashtable_t *self, rx_hash_node_t *first, rx_hash_node_t *last)
{
		RX_ASSERT(__hashtable_is_valid(self));
		
		while(first != NULL && first != last)
		{
				first = rx_hashtable_erase_node(self, first);
		}
		return first;
}


rx_hash_node_t* rx_hashtable_find(const rx_hashtable_t *self, const void *key)
{
		rx_hash_node_t *curr;
		size_t idx;
		RX_ASSERT(__hashtable_is_valid(self));
		idx = __calc_bknum_key(self, key);
		curr = self->buckets[idx];

		while(curr != NULL)
		{
				if(self->info.cmp_f(key, self->info.key_f(__hash_node_data(curr)), self->info.key_elem_size) == 0)
				{
						return curr;
				}else
				{
						curr = curr->next;
				}
		}

		return NULL;
}



size_t			 rx_hashtable_node_count(const rx_hashtable_t *self, const void *key)
{
		size_t n;
		rx_hash_node_t *first;
		RX_ASSERT(__hashtable_is_valid(self));
		
		
		first = rx_hashtable_find(self,key);
		n = 0;
		while(first != NULL && self->info.cmp_f(self->info.key_f(__hash_node_data(first)), key, self->info.key_elem_size) == 0)
		{
				first = rx_hashtable_node_next(self, first);
				n++;
		}

		return n;
}


size_t	rx_hashtable_erase_key(rx_hashtable_t *self, const void *key)
{
		size_t n;
		rx_hash_node_t *first;
		RX_ASSERT(__hashtable_is_valid(self));
		
		first = rx_hashtable_find(self,key);
		n = 0;
		while(first != NULL && self->info.cmp_f(self->info.key_f(__hash_node_data(first)), key,self->info.key_elem_size) == 0)
		{
				first = rx_hashtable_erase_node(self, first);
				n++;
		}

		return n;



}










rx_hashtable_t* rx_hashtable_create(const rx_info_t *info, const rx_alloc_t *palloc)
{
		rx_hashtable_t* res = NULL;
		
		if(palloc == NULL)palloc = rx_mem_default_alloctor();

		res = (rx_hashtable_t*)palloc->alloc_f(sizeof(rx_hashtable_t), palloc->ctx);

		RX_FATAL_ERROR(res != NULL);
		
		rx_memset(res, 0, sizeof(rx_hashtable_t));
		RX_ASSERT(info != NULL);

		res->info = *info;
		res->alloc = *palloc;
		rx_install_info(&res->info);
		RX_ASSERT(__hashtable_is_valid(res));
		return res;
}


void			 rx_hashtable_destroy(rx_hashtable_t *self)
{
		if(self != NULL)
		{
				RX_ASSERT(__hashtable_is_valid(self));

				rx_hashtable_clear(self);
				__clear_free_nodes(self);
				self->alloc.dealloc_f(self, self->alloc.ctx);
		}
}


size_t			 rx_hashtable_size(const rx_hashtable_t *self)
{
		RX_ASSERT(__hashtable_is_valid(self));
		return self->elem_count;
}

void			 rx_hashtable_clear(rx_hashtable_t *self)
{
		size_t i;
		RX_ASSERT(__hashtable_is_valid(self));

		for(i = 0; i < self->bucket_size; ++i)
		{
				rx_hash_node_t *curr = self->buckets[i], *tmp;
				while(curr != NULL)
				{
						tmp = curr;
						curr = curr->next;
						__destroy_node(tmp, self);
				}
				self->buckets[i] = NULL;
		}
		self->elem_count = 0;
}





rx_hashtable_t* rx_hashtable_copy(const rx_hashtable_t *self)
{
		size_t idx;
		rx_hash_node_t	**new_buks;
		rx_hashtable_t* new_t;
		RX_ASSERT(__hashtable_is_valid(self));
		
		new_t = rx_hashtable_create(&self->info, &self->alloc);
		new_buks = NULL;

		if(self->bucket_size > 0)
		{
				new_buks = (rx_hash_node_t**)self->alloc.alloc_f(sizeof(rx_hash_node_t*) * self->bucket_size, self->alloc.ctx);
				RX_FATAL_ERROR(new_buks != NULL);
		}
		
		for(idx = 0; idx < self->bucket_size; ++idx)new_buks[idx] = NULL;

		for(idx = 0; idx < self->bucket_size; ++idx)
		{
				rx_hash_node_t *curr, *cpy_node;
				if(self->buckets[idx] == NULL)continue;

				
				curr = self->buckets[idx];
				new_buks[idx] = __create_node(__hash_node_data(curr), new_t);
				cpy_node = new_buks[idx];
				curr = curr->next;
				
				while(curr != NULL)
				{
						cpy_node->next = __create_node(__hash_node_data(curr),new_t);
						cpy_node = cpy_node->next;
						curr = curr->next;
				}
		}
		new_t->buckets = new_buks;
		new_t->bucket_size = self->bucket_size;
		new_t->elem_count = self->elem_count;
		RX_ASSERT(__hashtable_is_valid(self));
		return new_t;
}












RX_SPACE_END
